package com.wuda.util;

/**
 * <p>
 * 有序队列,默认是降序排列元素.如果调用{@link #next()}方法则是从前往后遍历;如果调用{@link #previous()}则是从后往前遍历.
 * 通过调用 {@link #resetIterate()}方法,可以反复从前或者从后开始遍历.因为是双链表,所以从前往后和从后往前的时间复杂度是一样的
 * </p>
 * 
 * @author wuda
 * 
 */
public class PriorityLinkedQueue<T extends Comparable<T>> {

	/**
	 * 队列的排序方向
	 */
	private Order order = Order.DESC;

	/**
	 * 队列的容量,主要是用于固定元素的队列
	 */
	private int capacity;
	private boolean fixedSize = false;

	/**
	 * 队列中实际的元素个数
	 */
	private int size = 0;

	/**
	 * 只占一个位置,不是实际添加的元素
	 */
	private Entry header = new Entry(null, null, null);

	/**
	 * 用于{@link PriorityLinkedQueue#next()}方法标识当前已经遍历的元素
	 */
	private Entry current = header;
	private boolean iterateComplete = false;// 一次完整的遍历是否完成

	/**
	 * 顺序
	 * 
	 * @author wuda
	 * 
	 */
	public static enum Order {
		DESC, ASC;
	}

	/**
	 * <p>
	 * 元素个数固定的有序队列
	 * </p>
	 * 
	 * @param capacity
	 *            容量,如果是小于1的整数则表示元素个数不受现在
	 * @param order
	 *            排序顺序
	 */
	public PriorityLinkedQueue(int capacity, Order order) {
		this.capacity = capacity;
		if (capacity < 1) {
			this.fixedSize = false;
		} else {
			this.fixedSize = true;
		}
		this.order = order;
	}

	/**
	 * <p>
	 * 添加元素
	 * </p>
	 * 
	 * @param element
	 *            T 不能为null
	 */
	public void add(T element) {
		if (element == null) {
			return;
		}
		Entry e = new Entry(element, null, null);
		if (size == 0) {
			header.next = e;
			header.previous = e;

			e.next = header;
			e.previous = header;
			size++;
			return;
		}
		Entry threshold = header.previous;
		switch (order) {
		case DESC:
			while (threshold != header
					&& element.compareTo(threshold.element) > 0) {
				threshold = threshold.previous;
			}
			break;
		case ASC:
			while (threshold != header
					&& element.compareTo(threshold.element) < 0) {
				threshold = threshold.previous;
			}
			break;
		}

		e.next = threshold.next;
		e.previous = threshold;

		threshold.next.previous = e;
		threshold.next = e;
		size++;
		if (fixedSize && size > capacity) {
			/**
			 * 删除最后一个元素的链接,以前的倒数第二个成为最后一个
			 */
			header.previous.previous.next = header;
			header.previous = header.previous.previous;
			size--;
		}
	}

	/**
	 * 从头开始遍历这个队列,调用{@link #resetIterate()}方法可以重新从头开始遍历
	 * 
	 * @return T 当返回为null时,队列遍历完成
	 */
	public T next() {
		if (size == 0 || iterateComplete) {
			return null;
		}
		Entry e = current.next;
		if (e == header) {// 从header开始又来到header,则一次完整的遍历完成
			iterateComplete = true;
			return null;
		}
		T element = e.element;
		current = e;
		return element;
	}

	/**
	 * 从尾部开始遍历这个队列,调用{@link #resetIterate()}方法可以重新从尾部开始遍历
	 * 
	 * @return T 当返回为null时,队列全部变量遍历
	 */
	public T previous() {
		if (iterateComplete) {
			return null;
		}
		Entry e = current.previous;
		if (e == header) {// 从header开始又来到header,则一次完整的遍历完成
			iterateComplete = true;
			return null;
		}
		T element = e.element;
		current = e;
		return element;
	}

	/**
	 * 重新从头或者从尾部开始遍历
	 */
	public void resetIterate() {
		current = header;
		iterateComplete = false;
	}

	class Entry {
		T element;
		Entry next;
		Entry previous;

		Entry(T element, Entry next, Entry previous) {
			this.element = element;
			this.next = next;
			this.previous = previous;
		}
	}
}
